package com.shm.leetcode;

/**
 * 459. 重复的子字符串
 * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
 *
 * 示例 1:
 *
 * 输入: "abab"
 *
 * 输出: True
 *
 * 解释: 可由子字符串 "ab" 重复两次构成。
 * 示例 2:
 *
 * 输入: "aba"
 *
 * 输出: False
 * 示例 3:
 *
 * 输入: "abcabcabcabc"
 *
 * 输出: True
 *
 * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 * @author SHM
 */
public class RepeatedSubstringPattern {
    /**
     *
     * 方法二：字符串匹配
     * 思路与算法
     *
     * 我们可以把字符串 ss 写成
     *
     * s's' \cdots s's'
     * s
     * ′
     *  s
     * ′
     *  ⋯s
     * ′
     *  s
     * ′
     *
     *
     * 的形式，总计 \frac{n}{n'}
     * n
     * ′
     *
     * n
     * ​
     *   个 s's
     * ′
     *  。但我们如何在不枚举 n'n
     * ′
     *   的情况下，判断 ss 是否能写成上述的形式呢？
     *
     * 如果我们移除字符串 ss 的前 n'n
     * ′
     *   个字符（即一个完整的 s's
     * ′
     *  ），再将这些字符保持顺序添加到剩余字符串的末尾，那么得到的字符串仍然是 ss。由于 1 \leq n' < n1≤n
     * ′
     *  <n，那么如果将两个 ss 连在一起，并移除第一个和最后一个字符，那么得到的字符串一定包含 ss，即 ss 是它的一个子串。
     *
     * 因此我们可以考虑这种方法：我们将两个 ss 连在一起，并移除第一个和最后一个字符。如果 ss 是该字符串的子串，那么 ss 就满足题目要求。
     *
     * 注意到我们证明的是如果 ss 满足题目要求，那么 ss 有这样的性质，而我们使用的方法却是如果 ss 有这样的性质，那么 ss 满足题目要求。因此，只证明了充分性是远远不够的，我们还需要证明必要性。
     *
     * 题解区的很多题解都忽略了这一点，但它是非常重要的。
     *
     * 证明需要使用一些同余运算的小技巧，可以见方法三之后的「正确性证明」部分。这里先假设我们已经完成了证明，这样就可以使用非常简短的代码完成本题。在下面的代码中，我们可以从位置 11 开始查询，并希望查询结果不为位置 nn，这与移除字符串的第一个和最后一个字符是等价的。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern(String s) {
        return (s+s).indexOf(s,1) != s.length();
    }

    /**
     * 方法一：枚举
     * 思路与算法
     *
     * 如果一个长度为 nn 的字符串 ss 可以由它的一个长度为 n'n
     * ′
     *   的子串 s's
     * ′
     *   重复多次构成，那么：
     *
     * nn 一定是 n'n
     * ′
     *   的倍数；
     *
     * s's
     * ′
     *   一定是 ss 的前缀；
     *
     * 对于任意的 i \in [n', n)i∈[n
     * ′
     *  ,n)，有 s[i] = s[i-n']s[i]=s[i−n
     * ′
     *  ]。
     *
     * 也就是说，ss 中长度为 n'n
     * ′
     *   的前缀就是 s's
     * ′
     *  ，并且在这之后的每一个位置上的字符 s[i]s[i]，都需要与它之前的第 n'n
     * ′
     *   个字符 s[i-n']s[i−n
     * ′
     *  ] 相同。
     *
     * 因此，我们可以从小到大枚举 n'n
     * ′
     *  ，并对字符串 ss 进行遍历，进行上述的判断。注意到一个小优化是，因为子串至少需要重复一次，所以 n'n
     * ′
     *   不会大于 nn 的一半，我们只需要在 [1, \frac{n}{2}][1,
     * 2
     * n
     * ​
     *  ] 的范围内枚举 n'n
     * ′
     *   即可。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n^2)O(n
     * 2
     *  )，其中 nn 是字符串 ss 的长度。枚举 ii 的时间复杂度为 O(n)O(n)，遍历 ss 的时间复杂度为 O(n)O(n)，相乘即为总时间复杂度。
     *
     * 空间复杂度：O(1)O(1)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern_2(String s) {
        int n = s.length();
        for(int i=1;i*2<=n;i++){
            if(n%i==0){
                boolean match = true;
                for(int j=i;j<n;j++){
                    if(s.charAt(j)!=s.charAt(j-i)){
                        match = false;
                        break;
                    }
                }
                if(match){
                    return true;
                }
            }
        }
        return false;
    }
}
